[백준]단계별풀이_재귀
💯 solving-algo | February 19, 2021
10872번: 팩토리얼
import sys
input = sys.stdin.readline()
n = int(input)
def factorial(n):
if n == 0:
return 1
elif n == 1:
return 1
return n * factorial(n-1)10870번: 피보나치 수 5
for문 이용
import sys
input = sys.stdin.readline()
n = int(input)
def fibo(n):
result = []
first = 1
second = 1
if n > 1:
result.append(first)
result.append(second)
for _ in range(2, n):
third = first + second
first = second
second = third
result.append(third)
return result.pop()
print(fibo(n))recursive func 이용
import sys
input = sys.stdin.readline()
n = int(input)
def fibo(n):
if n <= 1:
return n
return fibo(n - 2) + fibo(n - 1)
print(fibo(n))- 이런 식의 코드를 짜게 된다면, 이미 이전에 계산했던 불필요한 계산을 한번 더 하게된다.
- 그래서
memoization(메모이제이션) 을 통해 임의의list에다가 메모를 해 답을 도출해 내는 것이 훨씬 빠르다.
recursive func + memoization 이용
import sys
input = sys.stdin.readline()
n = int(input)
def fibo(n, lookup):
if n <= 1:
return n
# lookup[n]이 없을 때 None일 때 계산해서 넣는 로직
if lookup[n] is None:
lookup[n] = fibo(n-2, lookup) + fibo(n-1, lookup)
return lookup[n]
lookup = [None] * (n + 1)
print(fibo(n, lookup))